Related subject matter is disclosed in the co-pending, commonly assigned, U.S. Patent application of Ahmed et al., entitled xe2x80x9cA Topology Sensing Scheme for Networks with Mobile Nodes,xe2x80x9d Application No. 09/513,325, filed on Feb. 25, 2000.
This invention relates generally to communications and, more particularly, to wireless systems.
An xe2x80x9cad-hocxe2x80x9d mobile network (ad-hoc network) is a wireless network that comprises a collection of nodes whose positions are continually changing. Unlike a regular wireless network, one can view an ad-hoc network as a network with no fixed infrastructure. For example, all the nodes function as routers and perhaps as base stations; and the mobility of the nodes causes frequent changes in network topology.
It is the varying network topology of an ad-hoc network that causes difficulty in applying routing techniques used in a conventional wireless network. In the latter, the nodes in the network are stationary and the links connecting the nodes go down infrequently. As such, it is possible to maintain the whole network topology at each node by sending topology-related information to all the nodes in the network via, what is known in the art as, xe2x80x9clink-state,xe2x80x9d updates. Since nodes go down infrequentlyxe2x80x94link-state updates are infrequentxe2x80x94and this approach works quite well in a conventional wireless network. However, in an ad-hoc network link-state changes are more frequent because of the shifting topology, thus generating many more link-state update messages throughout the ad-hoc networkxe2x80x94and consuming valuable bandwidth in the process. Also, construction of consistent routing tables is difficult because of the delay involved in propagating link-state information.
Considering these factors, routing protocols for ad-hoc networks can be classified broadly into two categories: xe2x80x9ctable-drivenxe2x80x9d and xe2x80x9csource initiated on-demand.xe2x80x9d Table-driven routing protocols are similar to the above-mentioned conventional wireless routing approach, i.e., each node attempts to maintain consistent, up-to-date, routing information for all other nodes in the network. Examples of table driven routing protocols are xe2x80x9cDestination-Sequenced-Distance-Vectorxe2x80x9d (DSDV), xe2x80x9cClusterhead Gateway Switch Routingxe2x80x9d (CGSR), and the xe2x80x9cWireless Routing Protocolxe2x80x9d (WRP) protocols. In contrast, source initiated on-demand routing protocols create routing information only when a source node needs a route to a given destination. Examples of source initiated on-demand routing protocols include xe2x80x9cAd-Hoc On-Demand Distance Vectorxe2x80x9d (AODV), xe2x80x9cDynamic Source Routingxe2x80x9d (DSR), xe2x80x9cTemporally Ordered Routing Algorithmxe2x80x9d (TORA), and the xe2x80x9cZone Routing Protocolxe2x80x9d (ZRP) protocol.
As an illustration of a source initiated on-demand protocol consider ZRP. In ZRP, each node maintains the whole network topology for a local area, or zone, around it. As such, if the node (i.e., the source node) has to send a packet to a destination address in the zone, that routing information is already available. However, if the source node has to send a packet to a destination address outside their zone, then the node initiates a query to all the nodes in the edge of its zone (i.e., edge nodes). If one of these edge nodes has the routing information for the destination address, then that routing information is passed on back to the source node.
We have observed that the above-mentioned forms of ad-hoc network routing protocols generally require a node maintaining accurate information, in one form or another, about how to route to a node in regions that are far away from it. As such, if the number of nodes is large and spread over a large geographical area, and if there is reasonable mobility of the nodes, getting this information becomes difficultxe2x80x94if not impractical. Therefore, and in accordance with the invention, a source node uses a geometry-based routing protocol (GRP) to route traffic to a destination node. In the GRP, a source node routes a packet to a destination node outside of its local node topology (referred to herein as the local topology) as a function of the distance to the destination node.
In an embodiment of the invention, a source node maintains location information and routing information for all nodes in a local area, or local topology, and at least approximate location information for at least some nodes outside the local area. If the source node has to send a packet to a destination node in their local area, that routing information is already available. However, if the source node has to send a packet to a destination node outside their local area, then the source node uses the approximate location information of the destination node to identify which node in the local area is closest to the destination node in the local topology. If the identified local node is different from the source node, the latter transmits the packet to the identified local node, which then attempts to route the packet to the destination node. Otherwise, the packet is dropped.